package linkList

import (
	"fmt"
)

//the struct of single list
type LNode struct{
	Next *LNode
	Data int
}

func NewListHeader() *LNode{
	return &LNode{}
}

//Reverse reverse the order of single list
func (n *LNode)Reverse(){
	if n == nil || n.Next == nil {
		return
	}

	//我们从第一个节点开始执行
	var cur = n.Next
	var next = cur.Next
	var tmp *LNode

	for cur != nil {
		next = cur.Next
		cur.Next = tmp
		tmp = cur
		cur = next
	}
	n.Next = tmp
}

//Reverse reverse the order of single list
func (n *LNode)ReverseInsertAfterNode(){
	if n == nil || n.Next == nil {
		return
	}

	//我们从第一个节点开始执行
	var cur = n.Next
	var next = cur.Next
	n.Next = nil

	for cur != nil {
		next = cur.Next
		cur.Next = n.Next
		n.Next = cur
		cur = next
	}
}

//RecursionReverseChild
func (n *LNode) RecursionReverseChild() {
	if n == nil || n.Next == nil || n.Next.Next == nil {
		return
	}
	cur := n.Next
	//子链表的开头将变为原来的结尾
	child := n.Next.Next
	//头结点指向排过序的子节点，cur节点作为头结点，将子链表排序
	cur.RecursionReverseChild()

	n.Next = cur.Next
	//最后的元素要指向nil
	cur.Next = nil
	child.Next = cur

	return
}

func (n *LNode)Print(){
	var cur *LNode = n.Next
	for cur != nil {
		fmt.Printf("%d", cur.Data)
		cur = cur.Next
	}
	fmt.Println()
}

func (n *LNode)GenListInOrder(num int){
	for i := num; i > 0; i-- {
		new := &LNode{}
		new.Data = i
		new.Next = n.Next
		n.Next = new
	}
}
/*
func main(){
	head := &LNode{}

	head.Print()
	head.Reverse()
	head.Print()
}
*/

func (n *LNode) GenWithSlice(s []int) {
	pre := n
	for _, d := range s {
		pre.Next = &LNode{
			Next: nil,
			Data: d,
		}
		pre = pre.Next
	}
}

//DeleteDuplicateElementDirectInOrder 直接从链表中顺序删除
func (n *LNode) DeleteDuplicateElementDirectInOrder() {
	if n == nil || n.Next == nil {
		return
	}
	curOut := n.Next
	for curOut != nil {
		curIn := curOut.Next
		preIn := curOut
		for curIn != nil {
			if curIn.Data == curOut.Data {
				preIn.Next = curIn.Next
				curIn = curIn.Next
			}else{
				preIn = curIn
				curIn =curIn.Next
			}
		}
		curOut = curOut.Next
	}
}

func (n *LNode) DeleteDuplicateEleRecursion() {
	if n == nil || n.Next == nil {
		return
	}
	cur := n.Next
	childHead := cur
	childHead.DeleteDuplicateEleRecursion()

	child := childHead.Next
	childPre := childHead
	for child != nil {
		if child.Data == cur.Data {
			//为了保持顺序，将子链表中的数据删除,子链表中只会有一个重复的数据
			childPre.Next = child.Next
			break
		}
		childPre = child
		child = child.Next
	}
}

func (n *LNode) DeleteDuplicateEleByHashMap() {
	if n == nil || n.Next == nil {
		return
	}
	pre := n
	cur := n.Next
	dir := make(map[int]bool, 10)
	for cur != nil {
		if dir[cur.Data] {
			pre.Next = cur.Next
		}else{
			dir[cur.Data] = true
		}
		pre = cur
		cur = cur.Next
	}
}

//仅仅做填充，返回是否填充后还需要进位
func fillIntoSum(d *LNode, s *LNode, carryBit int) (*LNode, int) {
	if d == nil || s == nil {
		return d, carryBit
	}

	for s != nil {
		d.Next = &LNode{}
		d = d.Next
		d.Data = (s.Data + carryBit) % 10
		if s.Data + carryBit >= 10 {
			carryBit = 1
		}else{
			carryBit = 0
		}
		s = s.Next
	}
	return d, carryBit
}

func SumTwoList(a *LNode, b *LNode) (sum *LNode) {
	carryBit := 0
	sum = NewListHeader()
	sumCur := sum
	aCur := a.Next
	bCur := b.Next

	for aCur != nil && bCur != nil {
		sumCur.Next = &LNode{}
		sumCur = sumCur.Next
		sumCur.Data = (aCur.Data + bCur.Data + carryBit) % 10
		if aCur.Data + bCur.Data + carryBit >= 10 {
			carryBit = 1
		}else{
			carryBit = 0
		}
		aCur = aCur.Next
		bCur = bCur.Next
	}
	if aCur != nil {
		sumCur, carryBit = fillIntoSum(sumCur, aCur, carryBit)
	}
	if bCur != nil {
		sumCur, carryBit = fillIntoSum(sumCur, bCur, carryBit)
	}
	if carryBit != 0 {
		sumCur.Next = &LNode{}
		sumCur = sumCur.Next
		sumCur.Data = 1
	}
	return sum
}

func ReverseWithoutHeader(n *LNode) *LNode {
	if n == nil || n.Next == nil {
		return n
	}
	var pre *LNode
	var next *LNode

	for n != nil {
		next = n.Next
		n.Next = pre
		pre = n
		n = next
	}
	return pre
}

//find pre node of middle node
func (n *LNode) FindMiddleNode() *LNode {
	if n == nil || n.Next == nil {
		return n
	}
	slow := n
	quick := n
	slowPre := n
	for quick != nil && quick.Next != nil {
		quick = quick.Next.Next
		slowPre = slow
		slow = slow.Next
	}
	return slowPre
}

func (n *LNode)Interspersed() {
	if n == nil || n.Next == nil {
		return
	}
	midPre := n.FindMiddleNode()
	mid := midPre.Next
	midPre.Next = nil
	mid = ReverseWithoutHeader(mid)
	lCur := n.Next
	var tmp *LNode
	//mid的数量总是比左边的数量多的
	for lCur != nil {
		tmp = lCur.Next
		lCur.Next = mid
		lCur = tmp
		tmp = mid.Next
		mid.Next = lCur
		mid = tmp
	}
}


func (n *LNode) FindTheNthNodeFromBottom(number int) *LNode {
	if n == nil || n.Next == nil {
		return nil
	}
	//让快指针先走number步后，再让慢指针走，当快指针指向nil时，慢指针指向的节点为想要的节点
	var slow *LNode
	var fast = n.Next
	for fast != nil && number > 0 {
		fast = fast.Next
		number--
	}
	//如果number大于0则意味着链表中的元素不超过n个，倒数第number个元素不存在
	if number > 0 {
		return nil
	}
	slow = n.Next
	for fast != nil {
		fast = fast.Next
		slow = slow.Next
	}

	return slow
}

func (n *LNode) RotateN(number int) {
	if n == nil || n.Next == nil || number ==0 {
		return
	}
	//让快指针先走number步后，再让慢指针走，当快指针指向nil时，慢指针指向的节点为想要的节点
	var slow *LNode
	var fast = n.Next
	for fast != nil && number > 0 {
		fast = fast.Next
		number--
	}
	//如果fast==nil意味着链表中最多有number个元素，不需要旋转
	if fast == nil {
		return
	}
	slow = n.Next
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	tmp := n.Next
	n.Next = slow.Next
	slow.Next = nil
	fast.Next = tmp
	return
}

func (n *LNode) IsLoop() *LNode {
	if n == nil || n.Next == nil {
		return nil
	}

	var fast = n.Next
	var slow = n.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if fast == slow {
			return slow
		}
	}
	return nil
}

/*
	假设相遇后slow指针走了s步，fast指针走了2s步，假设环长为r
	2s = s + nr
	s = nr
	假设环入口与相遇点距离为x，起点到环入口点为a
	a + x = s
	a + x = nr
	即a = nr - x，意味着a,x同步增加，迟早会在环的入口相遇
*/
func (n *LNode)FindLoopEnter(lastMeet *LNode) *LNode {
	if n == nil || lastMeet == nil {
		return nil
	}
	tmp1 := n.Next
	tmp2 := lastMeet
	for tmp1 != nil && tmp2 != nil {
		if tmp1 == tmp2 {
			return tmp1
		}
		tmp2 = tmp2.Next
		tmp1 = tmp1.Next
	}
	return nil
}

func (n *LNode)FindLoopEnterOnStep() *LNode {
	meet := n.IsLoop()
	if  meet == nil {
		return nil
	}
	return n.FindLoopEnter(meet)
}

func (n *LNode) ReverseNeighborNode() {
	if n == nil || n.Next == nil {
		return
	}
	cur := n.Next
	pre := n
	var next *LNode
	for cur != nil && cur.Next != nil {
		next = cur.Next.Next
		pre.Next = cur.Next
		cur.Next.Next = cur
		cur.Next = next
		pre = cur
		cur = next
	}
}

func (n *LNode) ReverseNumber(number int) {
	if n == nil || n.Next == nil {
		return
	}

	var begin = n.Next
	var end *LNode
	pre := n
	var next *LNode
	for begin != nil {
		end = begin
		//begin已经算作一个节点
		for i := 1; i < number; i++ {
			if end.Next != nil {
				end = end.Next
			} else {
				return
			}
		}
		next = end.Next
		end.Next = nil
		pre.Next = ReverseWithoutHeader(begin)
		begin.Next = next
		pre = begin
		begin = next
	}
}


//将有序链表b中的节点和a中的节点合并并返回
func MergeTwoLinkList(a *LNode, b *LNode) *LNode {
	if a == nil || a.Next == nil {
		return b
	}

	if b == nil || b.Next == nil {
		return a
	}
	pre := a
	curA := a.Next
	curB := b.Next
	var nextB *LNode
	for curA != nil && curB != nil {
		if curB.Data >= curA.Data {
			pre = curA
			curA = curA.Next
		}else{
			nextB = curB.Next
			pre.Next = curB
			curB.Next = curA
			pre = curB
			curB = nextB
			curA = pre.Next
		}
	}
	if curA == nil {
		pre.Next = curB
	}
	return a
}

//DeleteNodeWithOutPreNode 在不知道前驱节点的情况下删除本节点
func DeleteNodeWithOutPreNode(a *LNode)(){
	if a == nil || a.Next == nil {
		//如果这个节点是最后的一个节点，此节点无法删除
		return
	}
	next := a.Next
	a.Data = next.Data
	a.Next = next.Next
	return
}

//利用hashtable判断时候是否相交
func IfTwoNoLoopListIntersectByHash(a *LNode, b *LNode) bool {
	if a == nil || a.Next == nil || b == nil || b.Next == nil {
		return false
	}
	hashM := make(map[*LNode]bool, 10)
	aCur := a.Next
	bCur := b.Next
	for aCur != nil {
		hashM[aCur] = true
		aCur = aCur.Next
	}

	for bCur != nil {
		if hashM[bCur] == true {
			return true
		}
		bCur = bCur.Next
	}

	return false
}

//判断两个单链表是否交叉，两个链表均为有环链
func IfTwoLoopListIntersect(a *LNode, b *LNode) bool {
	enter1 := a.FindLoopEnterOnStep()
	if enter1 == nil {
		return false
	}
	enter2 := b.FindLoopEnterOnStep()
	if enter2 == nil {
		return false
	}
	if enter2 == enter1 {
		return true
	}
	return false
}

